Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

  1. Given nums = [1, 3, 5]
  3. sumRange(0, 2) -> 9
  4. update(1, 2)
  5. sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

Solution:

  1. public class NumArray {
  2.   int[] arr;    // stores nums[]
  3.   int[] BITree; // binary indexed tree
  5.   public NumArray(int[] nums) {
  6.     int n = nums.length;
  7.     arr = new int[n];
  8.     BITree = new int[n + 1];
  10.     for (int i = 0; i < n; i++) {
  11.       update(i, nums[i]); // init BITree[]
  12.       arr[i] = nums[i];   // init arr[]
  13.     }
  14.   }
  16.   void update(int i, int val) {
  17.     int diff = val - arr[i]; // get the diff
  18.     arr[i] = val;            // update arr[]
  20.     i++;
  21.     while (i <= arr.length) {
  22.       BITree[i] += diff; // update BITree[]
  23.       i += i & (-i);     // update index to that of parent
  24.     }
  25.   }
  27.   int getSum(int i) {
  28.     int sum = 0;
  30.     i++;
  31.     while (i > 0) {
  32.       sum += BITree[i]; // accumulate the sum
  33.       i -= i & (-i);    // move index to parent node
  34.     }
  35.     return sum;
  36.   }
  38.   public int sumRange(int i, int j) {
  39.     return getSum(j) - getSum(i - 1);
  40.   }
  41. }
  43. // Your NumArray object will be instantiated and called as such:
  44. // NumArray numArray = new NumArray(nums);
  45. // numArray.sumRange(0, 1);
  46. // numArray.update(1, 10);
  47. // numArray.sumRange(1, 2);